home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 2: Applications / Linux Cubed Series 2 - Applications.iso / math / graphs / graphed-.1 / graphed- / usr / local / graphed / include / sgraph / sgragra.h < prev    next >
Encoding:
C/C++ Source or Header  |  1995-07-10  |  5.6 KB  |  201 lines
  1. /* (C) Universitaet Passau 1986-1994 */
  2. /************************************************************************
  3.  * File    : sgragra.h                                      Version 1.0 *
  4.  * Aufgabe : Datenstruktur fuer Graphgrammatiken, aufbauend auf der    *
  5.  *           Standard-Datenstruktur Sgraph fuer Graphen.                *
  6.  * Autor   : Torsten Bachmann                        *
  7.  * Datum   : 18.12.90                            *
  8.  ************************************************************************/
  9.  
  10. #ifndef SGRAGRA_HEADER
  11. #define SGRAGRA_HEADER
  12.  
  13.  
  14.  
  15. /************************************************************************
  16.  *                                    *
  17.  *                alphabet-utilities                *
  18.  *                                    *
  19.  ************************************************************************/
  20.  
  21. extern    Slist    S_alphabet_append(Slist *alphabet, char *element);
  22. extern    Slist    S_alphabet_test  (Slist alphabet, char *element);
  23. extern    void    S_alphabet_remove(Slist alphabet);
  24.  
  25. #define Snode_label_is_terminal(sgragra, label) (S_alphabet_test((sgragra)->tv, (label)) != empty_slist)
  26. #define Snode_label_is_nonterminal(sgragra, label) (S_alphabet_test((sgragra)->nv, (label)) != empty_slist)
  27. #define Sedge_label_is_terminal(sgragra, label) (S_alphabet_test((sgragra)->te, (label)) != empty_slist)
  28. #define Sedge_label_is_nonterminal(sgragra, label) (S_alphabet_test((sgragra)->ne, (label)) != empty_slist)
  29.  
  30.  
  31. /************************************************************************
  32.  *                                    *
  33.  *                Sembed                    *
  34.  *                                    *
  35.  ************************************************************************/
  36.  
  37. #define S_out    0
  38. #define S_in    1
  39.  
  40. typedef struct sembed
  41. {
  42.     struct sembed    *pre, *suc;    /* Liste aller Regeln        */
  43.     struct sembed    *npre, *nsuc;    /* Einbettungen der Knoten    */
  44.     struct sprod    *prod;        /* "Vatergrammatik"        */
  45.  
  46.     Snode        node_right;    /* Knoten der rechten Seite    */
  47.     char        *node_embed;    /* Markierung des Knotens aus    */
  48.                     /* der Einbettung        */
  49.  
  50.     char        *oldedge;    /* Markierung der alten Kante    */
  51.     int             olddir;        /* Richtung der alten Kanten    */
  52.  
  53.     char        *newedge;    /* Markierung der neuen Kante    */
  54.     int        newdir;        /* Richtung der neuen Kante    */
  55.  
  56.     Attributes    attrs;
  57. }
  58.     *Sembed;
  59.  
  60.  
  61.  
  62. #define    empty_sembed    ((Sembed)NULL)
  63.  
  64. #define    for_all_sembeds(prod, emb) \
  65.     { if (((emb) = (prod)->embedding) != empty_sembed) do {
  66. #define    end_for_all_sembeds(prod, emb) \
  67.     } while (((emb) = (emb)->suc) != (prod)->embedding); }
  68.  
  69. #define    for_all_snode_sembeds(node, emb) \
  70.     { if (((emb) = (Sembed) node->embedding) \
  71.       != empty_sembed) do {
  72. #define    end_for_all_snode_sembeds(node, emb) \
  73.     } while (((emb) = (emb)->nsuc) != (Sembed) node->embedding); }
  74.  
  75.  
  76. /************************************************************************
  77.  *                                    *
  78.  *                  Sglobalembed                *
  79.  *                                    *
  80.  ************************************************************************/
  81.  
  82. typedef struct sglobalembed
  83. {    
  84.     struct sglobalembed    *pre, *suc;    /* Liste aller Regeln    */
  85.     struct sgragra        *gragra;    /* "Vaterproduktion"    */
  86.  
  87.     char        *node_right;
  88.     char        *node_embed;
  89.  
  90.     char        *oldedge;
  91.     int             olddir;    
  92.     
  93.     char        *newedge;
  94.     int        newdir;
  95.  
  96.     Attributes    attrs;
  97. }
  98.     *Sglobalembed;
  99.  
  100.  
  101.  
  102. #define    empty_sglobalembed    ((Sglobalembed)NULL)
  103.  
  104. #define    for_all_sglobalembeds(gragra, gemb) \
  105.     { if (((gemb) = (gragra)->global_embeddings) != empty_sglobalembed) do {
  106. #define    end_for_all_sglobalembeds(gragra, gemb) \
  107.     } while (((gemb) = (gemb)->suc) != (gragra)->global_embeddings); }
  108.  
  109.     
  110.  
  111. /************************************************************************
  112.  *                                    *
  113.  *                Sprod                    *
  114.  *                                    *
  115.  ************************************************************************/
  116.  
  117. typedef struct sprod
  118. {    struct sprod    *pre, *suc;    /* Liste der Produktionen    */
  119.     struct sgragra    *gragra;        /* "Vatergrammatik"        */
  120.  
  121.     char        *left;        /* linke Seite der Produktion    */
  122.     Sgraph        right;        /* rechte Seite            */
  123.     Sembed        embedding;    /* Einbettungsvorschrift    */
  124.     char        *label;
  125.     Attributes    attrs;
  126.  
  127.     char        *graphed_graph,
  128.             *graphed_left;
  129. }
  130.     *Sprod;
  131.  
  132. #define    empty_sprod    ((Sprod)NULL)
  133.  
  134. #define    for_all_sprods(gg, prod) \
  135.     { if (((prod) = (gg)->productions) != empty_sprod) do {
  136. #define    end_for_all_sprods(gg, prod) \
  137.     } while (((prod) = (prod)->suc) != (gg)->productions); }
  138.  
  139.  
  140. /************************************************************************
  141.  *                                    *
  142.  *                Sgragra                    *
  143.  *                                    *
  144.  ************************************************************************/
  145.  
  146. typedef enum 
  147. {    
  148.     S_UNDEFINED        = -1,
  149.  
  150.     S_GG            =  0,    /* the lowest bit determines       */
  151.     S_GG_UNDIRECTED        =  1,    /* the directedness of the grammar */
  152.     
  153.     S_NCE_1            =  2,
  154.     S_NCE_1_UNDIRECTED    =  3,
  155.     
  156.     S_NLC            =  4,
  157.     S_NLC_UNDIRECTED    =  5,
  158.     
  159.     S_BNLC            =  6,
  160.     S_BNLC_UNDIRECTED    =  7,
  161.     
  162.     S_ENCE_1        =  8,
  163.     S_ENCE_1_UNDIRECTED     =  9
  164.     
  165. }
  166.     Sgragra_type;
  167.  
  168. typedef struct sgragra
  169. {    Sgragra_type    class;        /* Grammatikklasse        */
  170.     Slist        tv, te;        /* Terminalzeichen        */
  171.     Slist        nv, ne;        /* Nichtterminalzeichen        */
  172.     Sprod        productions;    /* Liste der Produktionen    */
  173.     Sglobalembed    global_embeddings; 
  174.     Snode        startnode;    /* Startknoten aus nv        */
  175.     char         *label;
  176.     Attributes    attrs;
  177. }
  178.     *Sgragra;
  179.  
  180. #define    first_prod_in_sgragra(g)    ((g)->productions)
  181. #define    last_prod_in_sgragra(g)        ((g)->productions->pre)
  182. #define    empty_sgragra            ((Sgragra)NULL)
  183.  
  184.  
  185. extern    Sembed    make_sembed    (Sprod prod, Snode node);
  186. extern    void    remove_sembed    (Sembed embed);
  187.  
  188. extern    Sglobalembed    make_sglobalembed    (Sgragra gragra);
  189. extern    void        remove_sglobalembed    (Sglobalembed gembed);
  190.  
  191. extern    Sprod    make_sprod             (Sgragra gragra);
  192. extern    void    remove_sprod           (Sprod prod);
  193. extern    void    set_sprodlabel         (Sprod prod, char *label);
  194.  
  195. extern    Sgragra    make_sgragra     (void);
  196. extern    void    remove_sgragra   (Sgragra gragra);
  197. extern    void    set_sgragralabel (Sgragra gragra, char *label);
  198.  
  199.  
  200. #endif
  201.